# -*- coding: utf-8 -*-
# @Time    : 2019/3/25 14:03
# @Author  : Macher
# @File    : tree_search.py
# @Software: PyCharm Community Edition
# 建立二叉树进行优化

class Node(object):
    def __init__(self, element,rchild=None):
        self.element = element
        self.lchild = []
        self.rchild = rchild


class Tree(object):
    def __init__(self, root=None):
        self.root = root

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        else:
            queue = []
            queue.append(self.root)
            while queue:
                cur_node = queue.pop()
                # if cur_node.lchild is None:
                if abs(node.element - cur_node.rchild) >1:
                    cur_node.lchild += [].append(node.element)
                    return
                elif cur_node.rchild is None:
                    cur_node.rchild = node
                    return
                else:
                    queue.append(cur_node.lchild)
                    queue.append(cur_node.rchild)

    def width_circle(self):
        if self.root is None:
            return ' '
        else:
            queue = []
            queue.append(self.root)
            while queue:
                cur_node = queue.pop()
                try :
                    print(cur_node.element)
                    if cur_node.rchild is not None:
                        queue.append(cur_node.lchild)
                    if cur_node.rchild is not None:
                        queue.append(cur_node.rchild)
                except:continue

    def preorder(self, node):  # 递归每次遍历不同树
        if node == None:
            return
        print(node.element)
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        if node == None:
            return
        self.inorder(node.lchild)
        print(node.element)
        self.inorder(node.rchild)

    def postorder(self, node):
        if node == None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.element)

    def count(self,node,rchild):
        if abs(node - rchild) >1:
            return  True
        else:return False


if __name__ == '__main__':
    t = Tree()
    t.add(0)
    t.add(1)
    t.add(1.1)
    t.add(1.3)
    t.add(2)
    t.add(2.1)
    t.add(2.3)
    t.add(3)
    t.add(3.1)
    t.add(3.2)
    print(u"\n广度优先BFS")
    t.width_circle()
    print(u"\n前序遍历")
    t.preorder(t.root)
    print(u"\n中序遍历")
    t.inorder(t.root)
    print(u"\n后序遍历")
    t.postorder(t.root)


